package sort;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.concurrent.ThreadLocalRandom;

/**
 * 七大排序
 * @author yuisama
 * @date 2022/05/18 20:21
 **/
public class SevenSort {
    private static ThreadLocalRandom random = ThreadLocalRandom.current();
    public static void main(String[] args) {
        int n = 10000000;
        int[] arr = SortHelper.generaRandomArray(n,0,Integer.MAX_VALUE);
        int[] arr1 = SortHelper.arrCopy(arr);
        int[] arr2 = SortHelper.arrCopy(arr);
        int[] arr3 = SortHelper.arrCopy(arr);
        int[] arr4 = SortHelper.arrCopy(arr);
        int[] arr5 = SortHelper.arrCopy(arr);
//        SortHelper.testSort(arr,"selectionSort");
//        SortHelper.testSort(arr2,"selectionSortOP");
//        SortHelper.testSort(arr3,"insertionSort");
//        SortHelper.testSort(arr1,"insertionSortBS");
//        SortHelper.testSort(arr4,"shellSort");
        SortHelper.testSort(arr5,"heapSort");
        SortHelper.testSort(arr2,"mergeSort");
        SortHelper.testSort(arr1,"quickSort");
        SortHelper.testSort(arr3,"quickSortHoare");
    }

    public static void selectionSort(int[] arr) {
        // 最开始无序区间[i...n)
        // 有序区间[]
        // 最外层的for循环指的循环走的趟数，每走一趟外层循环，就有一个最小值放在了正确的位置
        for (int i = 0; i < arr.length - 1; i++) {
            // min指的是最小元素的索引下标
            int min = i;
            // 内层循环在查找当前无序区间的最小值索引
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    // j对应的元素比当前最小值还小
                    min = j;
                }
            }
            // min这个变量一定保存了当前无序区间的最小值索引
            // 有序区间[0..i) + 1
            // 无序区间[i..n) - 1
            swap(arr,i,min);
        }
    }

    /**
     * 双向选择排序
     * @param arr
     */
    public static void selectionSortOP(int[] arr) {
        int low = 0;
        int high = arr.length - 1;
        // low == high => 无序区间只剩下最后一个元素，其实整个数组已经有序了。
        while (low < high) {
            int min = low;
            int max = low;
            for (int i = low + 1; i <= high; i++) {
                if (arr[i] < arr[min]) {
                    min = i;
                }
                if (arr[i] > arr[max]) {
                    max = i;
                }
            }
            // 此时min对应了最小值索引，交换到无序区间的最前面
            swap(arr,min,low);
            // 边界条件 low == max
            if (max == low) {
                max = min;
            }
            swap(arr,max,high);
            low ++;
            high --;
        }
    }

    /**
     * 直接插入排序
     * 已排序区间[0..i)  => 默认第一个元素就是已经排好序的区间
     * 待排序区间[i...n)
     * @param arr
     */
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            // 已排序区间[0...1)
            // 待排序区间[i ..n)
            // 选择无序区间的第一个元素，不断向前看
            // 注意看内层循环的终止条件 j >= 1而不是 j >= 0 ?
            // 因为此时arr[j] 不断向前看一个元素  j - 1 要合法 j - 1 >= 0
            for (int j = i; j >= 1 && arr[j] < arr[j - 1]; j--) {
                swap(arr,j,j - 1);
//                // 边界
//                if (arr[j] > arr[j - 1]) {
//                    // arr[i] 恰好是有序区间的后一个元素，无序区间的第一个元素
//                    // 当前无序区间的第一个元素 > 有序区间最后一个元素
//                    break;
//                }else {
//                    swap(arr,j,j - 1);
//                }
            }
        }
    }

    /**
     * 二分插入排序
     * @param arr
     */
    public static void insertionSortBS(int[] arr) {
        // 有序区间[0..i)
        // 无序区间[i..n)
        for (int i = 0; i < arr.length; i++) {
            int val = arr[i];
            // 有序区间[left...right)
            int left = 0;
            int right = i;
            while (left < right) {
                int mid = (left + right) / 2;
                if (val < arr[mid]) {
                    right = mid;
                }else {
                    // val >= arr[mid]
                    left = mid + 1;
                }
            }
            // 搬移[left..i)的元素
            for (int j = i; j > left ; j--) {
                arr[j] = arr[j - 1];
            }
            // left就是待插入的位置
            arr[left] = val;
        }
    }

    /**
     * 希尔排序 - 缩小增量排序，按照gap将原数组分为gap个子数组，子数组内部先排序，不断缩小gap值，直到gap = 1
     * 当gap = 1时，整个数组已经近乎有序，只需要最后来一次插入排序即可
     * @param arr
     */
    public static void shellSort(int[] arr) {
        int gap = arr.length >> 1;
        // 预处理阶段
        while (gap >= 1) {
            // 按照gap分组之后，组内进行插入排序
            insertionSortByGap(arr,gap);
            gap = gap >> 1;
        }
    }

    /**
     * 大家极端情况，假设此时gap = 1
     * @param arr
     * @param gap
     */
    private static void insertionSortByGap(int[] arr, int gap) {
        // [9,1,2,5,7,4,8,6,3,5] gap = 5
        // i = 5
        for (int i = gap; i < arr.length; i++) {
            for (int j = i; j - gap >= 0 && arr[j] < arr[j - gap]; j -= gap) {
                swap(arr,j,j - gap);
            }
        }
    }

    /**
     * 归并排序
     * @param arr
     */
    public static void mergeSort(int[] arr) {
        mergeSortInternal(arr,0,arr.length - 1);
    }

    /**
     * 迭代实现归并排序(了解)
     * @param arr
     */
    public static void mergeSortNonRecursion(int[] arr) {
        // 最外层循环表示每次合并的子数组的元素个数
        // 子数组为1个元素，第二次循环2个元素，第三次循环合并4个元素，第四次8个元素 ..
        // 直到整个数组合并完成
        for (int sz = 1;sz <= arr.length ;sz += sz) {
            // 内存循环变量i就是每次合并操作的开始索引l
            // [8,6,2,3,1,5,7,4]  => [2,3,6,8]  [1,4,5,7]
            //                                             i
            for (int i = 0; i + sz < arr.length; i += sz + sz) {
                // 边界i + sz + sz - 1 > arr.length
                merge(arr,i,i + sz - 1,Math.min(i + sz + sz - 1,arr.length - 1));
            }
        }
    }

    /**
     * 在arr[l...r]上进行归并排序
     * @param arr
     * @param l
     * @param r
     */
    private static void mergeSortInternal(int[] arr, int l, int r) {
        // 2.小数组直接使用插入排序
        if (r - l <= 15) {
            insertionSort(arr,l,r);
            return;
        }
        // int mid = (l + r) / 2;
        // l = 2,r = 4  mid = 3 = 2 + (4 - 2) / 2 = 3
        int mid = l + ((r - l) / 2);
        mergeSortInternal(arr,l,mid);
        mergeSortInternal(arr,mid + 1,r);
        // arr[l..mid] 和 arr[mid + 1...r]有序 只需要合并这两个子数组即可
        // 1.到底什么时候才需要合并 arr[mid] < arr[mid + 1] 说明？arr[mid] 数组1的最大值 arr[mid + 1]数组2的最小值
        // 整个数组已经有序了，那你还合并个der
        if (arr[mid] > arr[mid + 1]) {
            // 前后两个子数组还存在乱序，才需要合并
            merge(arr,l,mid,r);
        }
    }

    /**
     * 在arr[l..r]上进行插入排序
     * @param arr
     * @param l
     * @param r
     */
    private static void insertionSort(int[] arr, int l, int r) {
        for (int i = l + 1; i <= r; i++) {
            for (int j = i; j >= l + 1 && arr[j] < arr[j - 1]; j--) {
                swap(arr,j,j - 1);
            }
        }
    }

    /**
     * 将有序子数组arr[l..mid] 和 有序arr[mid + 1...r] 合并为一个大的有序数组arr[l..r]
     * @param arr
     * @param l
     * @param mid
     * @param r
     */
    private static void merge(int[] arr, int l, int mid, int r) {
        // 先创建一个新的数组aux,将子数组的值复制给新数组
        int[] aux = new int[r - l + 1];
        // l = 2,r = 4
        // arr[2..4]
        // aux[0..2] 索引下标差了个l偏移量
        for (int i = 0; i < aux.length; i++) {
            // aux的索引下标0...arr.length - 1
            // arr的下标l...r
            aux[i] = arr[i + l];
        }
        // 数组1的开始下标
        int i = l;
        // 数组2的开始下标
        int j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                // 第一个数组已经遍历完毕
                arr[k] = aux[j - l];
                j ++;
            }else if (j > r) {
                // 第二个子数组遍历完毕
                arr[k] = aux[i - l];
                i ++;
            }else if (aux[i - l] <= aux[j - l]) {
                // 将aux[i - l]写回arr[k]
                arr[k] = aux[i - l];
                i ++;
            }else {
                // aux[i - l] > aux[j - l] 写回aux[j - l]
                arr[k] = aux[j - l];
                j ++;
            }
        }
    }

    public static void quickSort(int[] arr) {
        quickSortInternal(arr,0,arr.length - 1);
    }

    public static void quickSortNonRecursion(int[] arr) {
        Deque<Integer> stack = new ArrayDeque<>();
        // r
        stack.push(arr.length - 1);
        // l
        stack.push(0);
        // 每次从栈中取出两个元素，这辆个元素就是待排序区间的l..r
        while (!stack.isEmpty()) {
            int l = stack.pop();
            int r = stack.pop();
            if (l >= r) {
                // 当前子数组已经处理完毕
                continue;
            }
            int p = partition(arr,l,r);
            // 继续入栈两个子区间
            stack.push(p - 1);
            stack.push(l);

            stack.push(r);
            stack.push(p + 1);
        }
    }

    private static void quickSortInternal(int[] arr, int l, int r) {
        // 2.小区间上使用插入排序来优化，不用递归到底
        if (r - l <= 15) {
            insertionSort(arr,l,r);
            return;
        }
        int p = partition(arr,l,r);
        // 继续在左右两个子区间进行快速排序
        // 所有 < v的元素
        quickSortInternal(arr,l,p - 1);
        // 所有 >= v的元素
        quickSortInternal(arr,p + 1,r);
    }

    private static int partition(int[] arr, int l, int r) {
        // 1.优化1.使用一个随机位置作为分区点，避免快排在近乎有序数组上的性能退化
        int randomIndex = random.nextInt(l,r);
        swap(arr,l,randomIndex);
        int v = arr[l];
        // arr[l + 1..j] < v
        // 最开始区间没有元素
        int j = l;
        // arr[j + 1..i) >= v
        // 最开始大于区间也没有元素
        for (int i = l + 1; i <= r; i++) {
            if (arr[i] < v) {
                swap(arr,i,j + 1);
                j ++;
            }
        }
        // 此时元素j就是最后一个 < v的元素，就把v换到j的位置
        swap(arr,l,j);
        return j;
    }

    public static void quickSortHoare(int[] arr) {
        quickSortInternalHoare(arr,0,arr.length - 1);
    }

    private static void quickSortInternalHoare(int[] arr, int l, int r) {
        // 2.小区间上使用插入排序来优化，不用递归到底
        if (r - l <= 15) {
            insertionSort(arr,l,r);
            return;
        }
        int p = partitionHoare(arr,l,r);
        // 继续在左右两个子区间进行快速排序
        // 所有 < v的元素
        quickSortInternalHoare(arr,l,p - 1);
        // 所有 >= v的元素
        quickSortInternalHoare(arr,p + 1,r);
    }

    /**
     * 挖坑分区法
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private static int partitionHoare(int[] arr, int l, int r) {
        int randomIndex = random.nextInt(l,r);
        swap(arr,l,randomIndex);
        int pivot = arr[l];
        int i = l;
        int j = r;
        while (i < j) {
            // 先让j从后向前扫描到第一个 < v的元素停止
            while (i < j && arr[j] >= pivot) {
                j --;
            }
            arr[i] = arr[j];
            // 再让i从前向后扫描到第一个 > v的元素停止
            while (i < j && arr[i] <= pivot) {
                i ++;
            }
            arr[j] = arr[i];
        }
        arr[i] = pivot;
        return i;
    }

    /**
     * 冒泡排序
     * @param arr
     */
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean isSwaped = false;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr,j,j + 1);
                    isSwaped = true;
                }
            }
            if (!isSwaped) {
                // 内层没有元素交换，此时整个数组已经有序
                break;
            }
        }
    }


    // 原地堆排序
    public static void heapSort(int[] arr) {
        // 1.先将任意数组进行heapify调整为最大堆
        for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
            siftDown(arr,i,arr.length);
        }
        // 2.不断交换堆顶元素到数组末尾，每交换一个元素，就有一个元素落在了最终位置
        for (int i = arr.length - 1; i > 0; i--) {
            // arr[i] 就是未排序数组的最大值，交换末尾
            swap(arr,0,i);
            siftDown(arr,0,i);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 元素下沉操作
     * @param arr
     * @param i 下沉的索引
     * @param length 数组的长度
     */
    private static void siftDown(int[] arr, int i, int length) {
        while (2 * i + 1 < length) {
            int j = 2 * i + 1;
            if (j + 1 < length && arr[j + 1] > arr[j]) {
                j = j + 1;
            }
            if (arr[i] >arr[j]) {
                break;
            }else {
                swap(arr,i,j);
                i = j;
            }
        }
    }
}